package algorithm.search.binarysearch;

import algorithm.search.binarysearch.interfaces.ISearch;
import java.util.Random;

/**
 * @author: lancyguy
 * @author cgzh@hotmail.com
 * @param <T> type of the elements to be searched
 */
public class BinarySearcher<T> implements ISearch<T> {
    /**
     * constructor
     */
    public BinarySearcher(){

    }
    /**
     *
     * @param arr array to be searched
     * @param e search this value
     * @return index of the element equals e, if no element found then return -1
     */
    public int search(T[] arr, T e){
        int idx = search(arr,e,0,arr.length-1);
        return idx;
    }

    /**
     *
     * @param arr array to be searched
     * @param e search this value
     * @param head left boundary of the range of the array within which the searching takes place
     * @param end right boundary of the range of the array within which the searching takes place
     * @return index of the element equals e, if no element found, then return -1
     */
    public int search(T[] arr, T e, int head, int end){
        if(head==end) return arr[head].equals(e)?head:-1;
        int middle = (head+end)/2;
        int rl = search(arr,e,head,middle);
        if(rl>=0) return rl;
        int rr = search(arr,e,middle+1,end);
        return rr;
    }
}
class BinarySearchTester{
    private static Integer[] generateTestCase(int len, int sparseFactor){
        Integer[] arr = new Integer[len];
        for(int i=0;i<len;i++){
            arr[i] = new Integer(ran.nextInt(len * sparseFactor));
        }
        //ISort<Integer> sorter = new QuickSorter<Integer>();
        //sorter.sort(arr);
        return arr;
    }

    public static void main(String[] args){
        int len = 1000;
        int sparseFactor = 3;
        Integer foreigner = -1;
        int testTimes = 40;
        ISearch<Integer> searcher = new BinarySearcher<Integer>();
        NormalSearcher<Integer> checker = new NormalSearcher<Integer>();
        for(int i=0;i<testTimes;i++){
            Integer[] testCase = generateTestCase(len,sparseFactor);
            for (int j=0;j<len;j++){
                int result1 = searcher.search(testCase,testCase[j]);
                int[] expectResult1 = checker.searchAll(testCase,testCase[j]);
                Integer[] tempArr = new Integer[expectResult1.length];
                for(int k=0;k<expectResult1.length;k++)
                    tempArr[k] = expectResult1[k];
                if(checker.search(tempArr,result1)<0){
                    System.out.println("error on searching the value in position " + j + " of this array:");
                    for(Integer integer : testCase){
                        System.out.print(integer + " ");
                    }
                    System.out.println("");
                    System.out.println("returned: " + result1);
                    System.exit(0);
                }
                int result2 = searcher.search(testCase,foreigner);
                if(result2!=-1){
                    System.out.println("error on searching foreigner value of this array:");
                    for(Integer integer : testCase){
                        System.out.print(integer + " ");
                    }
                    System.out.println("");
                    System.out.println("returned: " + result2);
                    System.exit(0);
                }
            }
        }
        System.out.println("success!");
    }
    private static Random ran = new Random();
}
